package 练习题;


import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author Liangyaoyun
 */
public class RecoverFromPreorder {
    public static int i=0;
    public static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public static class Main {
        //通过先序遍历序列创建二叉树

        public static TreeNode createTree(String str) {
            TreeNode root = null;
            if (str.length()==i){
                return root;
            }
            if (str.charAt(i) != '#') {
                root = new TreeNode(str.charAt(i));
                i++;
                root.left = createTree(str);
                root.right = createTree(str);
            } else {
                i++;
            }
            return root;
        }

        public static void postorderTraversal(TreeNode root) {
            if (root==null){
                return ;
            }
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            System.out.print(root.val+" ");
        }
        public static void middleOrderTraversal(TreeNode root){
            if (root==null){
                return;
            }
            middleOrderTraversal(root.left);
            System.out.print(root.val+" ");
            middleOrderTraversal(root.right);
        }
        public static void  preorder( TreeNode root){
            if (root==null){
                return ;
            }
            System.out.print(root.val+" ");
            preorder(root.left);
            preorder(root.right);
        }

        //
        public static void main(String[] args) {
            Scanner sn = new Scanner(System.in);
            // 注意 hasNext 和 hasNextLine 的区别
            String str = sn.nextLine();
            TreeNode root = createTree(str);
            preorder(root);
            System.out.println();
            middleOrderTraversal(root);
            System.out.println();
            postorderTraversal(root);

        }
    }
}
